Computer and Modernization ›› 2013, Vol. 1 ›› Issue (4): 18-21.doi: 10.3969/j.issn.1006-2475.2013.04.005

• 人工智能 • Previous Articles     Next Articles

A Method for Determining Two Graphs’ Isomorphism Based on Dissimilarity of Subgraphs’ Vertex Valency

XIE Ke, WU Wen-quan, LIU Hong-jiang   

  1. Department of Computer Science, Aba Teachers College, Wenchuan 623002, China
  • Received:2012-11-28 Revised:1900-01-01 Online:2013-04-17 Published:2013-04-17

Abstract: 给出一个源于Ulam猜想的图同构的定理，基于该定理得到的同构算法可以借助子图的结点度数来寻找结点间的对应关系。对结点度数重复率不高的图可以极大减少其同构判定的时间复杂度。

Key words: This paper gives a theorem for graphs isomorphism that originates from the Ulam conjecture. Based on this theorem, the algorithm for determining graphs isomorphism can find out the bijection of vertexes by comparing the subgraphs’ vertex valency. Especially, this algorithm can reduce the time complexity for determining graphs isomorphism obviously within some graphs that have minor repeatability of vertex valency.

CLC Number: